Quicksort クイックソート
Sorting ソート 整列アルゴリズム Algorithmsの一種
分解し再帰的に解く分割統治法
配列 Arrayを適当に２つににわけて、それぞれをSorting ソート 整列し、２つをマージすることを繰り返す
分ける場所をpivot
分割A + pivot + 分割B
pivotの偏りで遅くなる
ピボット選択を乱択化
乱択アルゴリズム
特徴
O(n log n)
最悪時O(n**2)
偏りがある時→乱択アルゴリズム使う
in-place Algorithms内部ソート
安定ソートでない
交換する必要のある値だけを交換
早い、よく使われる
利点
in-place Algorithms
早い
table:quickSort
Name Best Average Worst Memory Stable Comments
Quick sort O(n log n) O(n log n) O(n log n) n No
実際・用途
実際どういうふうに使うの？
JavaScriptでいうととどれで使われてるの？
参考
JavaScript クイックソート - Qiita